An example of such digital calculation occurs in the calculation of the angular coordinate in a scan conversion from Cartesian to polar coordinates, as may be done for addressing television graphic display memory organized to be addressed in polar coordinates. The Cartesian coordinates x and y are directed from left to right and from top to bottom of screen, respectively, in the left-hand coordinate system customarily employed by television engineers; and it is convenient to choose the origin at the center of screen supposing the display memory is to cover the entire television screen. In any case, for the purposes of convenient scan conversion, the origins of the Cartesian-coordinate and polar-coordinate systems should preferably coincide at a point in image space. Radial polar coordinate r is measured outward from this point, and angular polar coordinate .theta. is measured turning about this point counterclockwise from positive half of x axis, in keeping with the use of left-hand coordinates.
The angular coordinate .theta. could be looked up from ROM responsive to x and y. Supposing the display to comprise 512 lines with 512 picture elements (or "pixels", for short) per line, then a quadrant of .theta. could be looked up from ROM using eight bits of x and eight bits of y as input. About fourteen bits of output are required to define .theta. with the resolution found by experiment to be required for extracting graphic images from display memory addressed in polar coordinates. The nine most significant bits of this angular coordinate are used together with eight bits of radial coordinate as input to a ROM storing a graphic image that fills the display screen, and five next most significant bits of this angular coordinate are used in two-dimensional interpolation between video samples from spatially adjacent locations in the ROM. This interpolation is done to avoid visible discontinuities in edges of the graphic image as it appears on the display screen. About sixty-four ROM's of the conventional size with eleven-bit imputs and eight-bit outputs would be required for such direct look-up of .theta..
The angular coordinate .theta. could be calculated by first dividing y and x and then using a ROM to look up tan.sup.-1 (y/x). Several division calculations must be carried on simultaneously to supply results at pixel scan rate unless one divides using ROM, which would require a ROM the size of that to look up directly from x and y. The size of the ROM required to look up tan.sup.-1 (y/x) has to be large enough to define y/x with enough bits to resolve the difference between 1/255 and 1/254 at one end of its range and between 254 and 255 at the other end of its range. This must require in excess of nine bits of input to memory, eight bits being required to define possible y values divided by x of unity and another bit to define their reciprocals, which values y/x would define the boundaries of quadrant defined by the lines x=255 and y=255 with the same resolution as pixels are defined on the display screen. Additional resolution in input to arc tangent table look-up ROM is certainly required to avoid spatial quantization effects at edges of the graphic image displayed on screen because some of the values of y/x will fall between those associated with those points on the boundary lines x=255, y=255.
Substantial still further resolution in input to arc tangent table look-up ROM is required because the non-linearity of the arc tangent function with respect to its argument is very marked as the argument becomes large. Manyfold increase in y/x causes only gradual increase in tan.sup.-1 (y/x). So excessive capability to resolve in this region reduces the number of bits available in y/x to resolve its arc tangent when (y/x) is small, and the number of bits of (y/x) to resolve .theta. adequately throughout the range of y/x must be increased.
The inventors have found that substantially less ROM is required if one looks up .theta. in ROM responsive to log.sub.2 (y/x) input as the tan.sup.-1 {anti-log [log.sub.2 (y/x)]}. This is because .theta. is more linear respective to log.sub.2 (y/x) than to y/x, so that adequate resolution in .theta. can be obtained through the full range of log.sub.2 y/x with fewer bits than through the full range of y/x.
More generally, if one has to look up a monotonically non-linear function of a variable from ROM, the number of bits required in the ROM input to adequately resolve the function across its whole range can be reduced if the variable is expressed in logarithmic terms. Where the monotonically non-linear function grows progressively more rapidly as the variable increases, then the more common form of logarithm, which increases as argument increases, is used. Where the monotonically non-linear function grows progressively less rapidly as the variable increases a form of logarithm which decreases as argument increase (e.g., as originally described by Napier) can be used.
This approach is particularly useful where the variable used as input to the ROM is the result of a calculation more easily carried forward in the logarithmic domain than in the linear domain. Digital division, such as that of y by x, is an example of such calculation. This can be done by subtracting the logarithm of x as obtained by table look-up from ROM from the logarithm of y as obtained by table look-up from ROM, which table look-ups can be performed sequentially from the same ROM. Or this can be done by adding the logarithm of y as obtained by table look-up from a ROM responsive to y input and the logarithm of 1/x as obtained by table look-up from a ROM responsive to x input. Types of calculation, besides digital division, that are more easily carried forward in the logarithmic domain than in the arithmetic include digital multiplication, certain power-taking and root-taking processes, and combinations of these operations.